#include <stdio.h>
#include <stdlib.h>
#define BLOCKSIZE  200//定义块的大小
#define COUNT 100  // 定义内存块总数 

enum STATUS {OCCUPIED,FREE//内存块的状态
		} block[COUNT]; //建立内存块数组 记录内存信息 

//进程链表
typedef struct ProcessInfo {
	int PId;  //记录进程ID 
	int pages; //记录页数 
	int * addr; //定义一个整形指针指向由动态数组构成的页面变换表 
	struct ProcessInfo * next;//链表指针指向下一个结点 
}P;
struct ProcessInfo *head;//定义链表头指针
void run();//程序菜单 
void Allocate(int id,int size);//为进程分配内存：参数（进程ID 和所需内存大小size） 
void Releace(int id);//释放一个进程所占的内存：参数（进程ID） 
void Locate(int id,int log);//查看进程的逻辑地址对应的物理地址：参数（进程ID，逻辑地址） 
void dispaly();//显示 进程单链表  
void mem(); //显示内存未被分配的块 
//看进程的逻辑地址对应的物理地址
void Locate(int id,int log){ 
	struct ProcessInfo *p_move;//定义一个结构体指针 用于遍历链表 
	int page,j;//page记录所在页数，j记录页内地址 
	p_move=head;
	j=log%BLOCKSIZE;
	while(p_move->PId!=id&&p_move->next!=NULL){//遍历链表 直到找到该进程或遍历整个链表后结束 
		p_move=p_move->next;
		} 
	if(p_move->PId==id){//判断是否找到 
		if(j==0) {//计算逻辑页号 
		page=log/BLOCKSIZE;
	}else	{
		page=log/BLOCKSIZE+1;
	}
		printf("物理地址为：%d\n",(p_move->addr[page-1])*BLOCKSIZE+j);//page-1是因为数组下标从零开始 而页号是从1开始 
	}
	else{
		printf("没有找到！！！\n");
	}
}
//遍历进程表 
void display() {
	P* p_move;
	p_move=head;
	printf("ID\tPages\n");
	while(p_move!=NULL) {//遍历整个单链表 
		printf("%d\t%d\n",p_move->PId,p_move->pages);
		p_move=p_move->next;
	}
}
//为进程分配内存 
void Allocate(int id,int size) {
	int pages,num=0,i,j;
	struct ProcessInfo *p_move,*p_new;//p_move 用于遍历数组 ，p_new用于保存进程信息 
	p_move=head;//将头指针的值传给p_move 
	while(p_move!=NULL) {//遍历整个链表判断ID是否有重复  
		if(p_move->PId==id) {
			printf("分配失败，进程ID相同！！！\n");
			return;//存在ID相同 退出插入 
		}
		p_move=p_move->next;//p_move指向下一个结点 
	}//计算分页的页数 
	if(size%BLOCKSIZE==0) {
		pages=size/BLOCKSIZE;
	}else
		pages=size/BLOCKSIZE+1; 
	for(i=0; i<COUNT; i++) {//遍历内存状态表查看空闲区是否足够 
		if(block[i]==FREE) {
			num++;
		}
		if(num>=pages)
			break;//若足够跳出循环 
	}

	if(num<pages) {//不够则退出插入 
		free(p_new); 
		printf("分配失败，空间不足!!\n");
		return;
	}
	p_new=(P *)malloc(sizeof(P));//对p_new进行初始化 
	p_new->PId=id;//将进程ID保存到p_new中 
	p_new->pages=pages;//将页面个数存入到p_new中 
	p_new->addr=(int *)malloc( sizeof(int)*pages );//申请pages个整形存储空间并将首地址传到addr中 
	for(i=0; i<pages; i++) {//为进程分配内存空间 
		for(j=0; j<COUNT; j++) {
			if(block[j]==FREE) {
				p_new->addr[i]=j;//将第i页对应内存块好存到addr[]中 
				block[j]=OCCUPIED;
				break;
			}
		}
	}
	p_move=head;//重新将链表首地址传给p_move 
	if(head==NULL) {//判断链表是否为空 
		head=p_new;// 将P_new的地址传给head 
		p_new->next=NULL;//p_new指向空 
	} else {
		while(p_move->next!=NULL) {//链表不为空则 找到最后一个节点 
			p_move=p_move->next;
		}
		p_move->next=p_new;//将p_new插入到最后一个节点后 
		p_new->next=NULL;//让p_new指向空 
	}
	printf("分配成功!!\n");
	return ;
}
//释放一个进程 
void Releace(int id) {
	struct ProcessInfo *p_move,*p_d;//p_move遍历链表 p_d保存被删除节点的前一个节点 
	int i;
	p_move=head;
	while(p_move->PId!=id&&p_move->next!=NULL){//遍历链表找到相应的进程 
		p_d=p_move;//p_d记录被删节点的前一个节点 
		p_move=p_d->next;
	} 
	if(p_move->PId==id){//判断是否找到 
		for(i=0;i<p_move->pages;i++){//遍历页面变换表释放相应的内存 
				block[p_move->addr[i]]=FREE;
		}
		free(p_move->addr);//释放页面变换表 
		if(p_move==head){//删除对应的节点 
			head=p_move->next;
			
		}else{
			p_d->next=p_move->next;
		}
		free(p_move);//释放被删除进程的节点 
		printf("删除成功！！！\n");
	}
	else{
		printf("没有找到！！！\n");
	}
}
//遍历内存块 查找未被分配的内存块 
void mem(){
	int i;
	printf("内存分区：");
	for(i=0;i<COUNT;i++){
		if(block[i]==FREE)
		printf("%d\t",i);
	}
	printf("\n"); 
}
void run() {
	int num,id,size;
	while(1) {
		display();
		size=0;
		id=-1;
		printf("**********************\n");
		printf("1：分配进程\t2:释放进程\t3：查看物理地址\t4:查看内存空闲内存块\t5:退出\n");
		scanf("%d",&num);
		switch(num) {
			case 1:
				printf("输入进程ID和所需内存空间大小:");
			 	scanf("%d %d",&id,&size);
				Allocate(id,size);
				break;
			case 2:
				printf("请输入进程ID：");
				scanf("%d",&id);
				Releace(id);
				break;
			case 3: 
			 	printf("输入进程ID和逻辑地址:");
			 	scanf("%d %d",&id,&size);
				Locate(id,size);
				break; 
			case 4: 
				mem();
				break;
			case 5:
				return ;
		}
		printf("**********************\n");
		
	}
}


int main() {
	int i;
	head=NULL;//初始化进程表 
	for(i=0; i< COUNT; i++) {//初始化内存块 
		block[i]=FREE;
	}
	run();
}